#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

const int oo=100000000;

int n;
int vv[1010];
int g[1010];
int num[10000], nxt[10000], c[10000], f[10000], v[10000], opp[10000], tot;
int h, t, q[1010], d[1010], fa1[1010], fa2[1010];
bool use[1010];

void insert( int x, int y, int cc, int vv ){
	tot++; num[tot]=y; nxt[tot]=g[x]; c[tot]=cc; f[tot]=0; v[tot]=vv; opp[tot]=tot+1; g[x]=tot;
	tot++; num[tot]=x; nxt[tot]=g[y]; c[tot]=0; f[tot]=0; v[tot]=-vv; opp[tot]=tot-1; g[y]=tot;
}

int flow( int st, int en ){
	int ans=0;
	while ( 1 ){
		memset( use, false, sizeof( use ) );
		memset( fa1, -1, sizeof( fa1 ) );
		for ( int i=0; i<=n+1; i++ ) d[i]=oo;
		h=0; t=1; q[1]=st; d[st]=0;
		while ( h!=t ){
			h++; if ( h==n+10 ) h=1;
			for ( int i=g[q[h]]; i!=0; i=nxt[i] )
				if ( c[i]>f[i] && d[q[h]]+v[i]<d[num[i]] ){
					d[num[i]]=d[q[h]]+v[i]; fa1[num[i]]=q[h]; fa2[num[i]]=i;
					if ( ! use[num[i]] ){
						t++; if ( t==n+10 ) t=1;
						q[t]=num[i]; use[num[i]]=true;
					}
				}
			use[q[h]]=false;
		}
		if ( d[en]==oo ) return ans;
		int tt=en, minn=oo;
		while ( fa1[tt]!=-1 ){
			if ( c[fa2[tt]]-f[fa2[tt]]<minn ) minn=c[fa2[tt]]-f[fa2[tt]];
			tt=fa1[tt];
		}
		tt=n+1;
		while ( fa1[tt]!=-1 ){
			f[fa2[tt]]+=minn;
			f[opp[fa2[tt]]]-=minn;
			tt=fa1[tt];
		}
		ans+=minn*d[n+1];
	}
}

int main(){
	int test=0;
	scanf("%d", &test);
	while ( test-- ){
		scanf("%d", &n);
		memset( g, 0, sizeof( g ) );
		tot=0;
		for ( int i=0; i<n; i++ ){
			scanf("%d", &vv[i]);
			insert( 0, i+1, vv[i], 0 );
			insert( i+1, n+1, 1, 0 );
		}
		for ( int i=0; i<n; i++ ){
			int pre=i-1, nxt=i+1;
			if ( pre<0 ) pre=n-1;
			if ( nxt==n ) nxt=0;
			insert( i+1, pre+1, oo, 1 );
			insert( i+1, nxt+1, oo, 1 );
		}
		printf("%d\n", flow( 0, n+1 ) );
	}
}
